package al41firstmissingpositive;

import java.util.Arrays;
import java.util.HashSet;

public class FirstMissingPositive {
/*
    // 暴力算法
    public static int firstMissingPositive(int[] nums) {
        int length = nums.length;
        if (length==1){
            return nums[0] == 1? nums[0]+1 : 1;
        }
        Arrays.sort(nums);
        if (nums[length-1] <0)
            return 1;
        boolean flag = false;
        int temp ;
        for(int i = 0;i< nums.length;i++){
            if(nums[i]>0 ){
                temp = i;
                if (nums[temp] !=1 && !flag){
                    return 1;
                }
                if(i!=length-1 &&nums[i+1]-nums[i]!= 1 && nums[i+1] !=nums[i]){
                    return nums[i]+1;
                }
                flag = true;
            }
        }
        return nums[length-1] + 1;
    }*/
    public static int firstMissingPositive(int[] nums) {
        int length = nums.length;

        for(int i=0;i<length;i++ ){
            if(nums[i]!=i+1){
                if(nums[i] > length)
                    continue;
                if(nums[i] <= 0)
                    continue;
                if(nums[i] == nums[nums[i]-1]&& nums[i]!=0)
                    continue;
                if(nums[i]==0 && i==length-1)
                    break;
                swap(nums,i,nums[i]-1);
                i--;
            }
        }
        for (int i = 0;i<length;i++){
            if(nums[i]!=i+1)
                return i+1;
        }
        return nums[length-1]+1;
    }

    public static void swap(int[] nums,int a,int b){
        int temp =0;
        temp = nums[b];
        nums[b] = nums[a];
        nums[a] = temp;
    }




    public static void main(String[] args) {
        int[] nums = {100000, 3, 4000, 2, 15, 1, 99999};
        int i = firstMissingPositive(nums);
        System.out.println(i);
    }

}
